package codingforgreat.class13;

public class Class03_ScrambleString {
    public static boolean isScramble(String s1, String s2) {
        if ((s1 == null && s2 != null) || (s1 != null && s2 == null)) {
            return false;
        }
        if (s1 == null && s2 == null) {
            return true;
        }
        if (s1.equals(s2)) {
            return true;
        }
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        if (!sameTypeSameNumber(str1, str2)) {
            return false;
        }
        return process(str1,0,str1.length - 1,str2,0,str2.length - 1);
    }
    public static boolean process(char[] str1,int L1,int R1,char[] str2,int L2,int R2){
        if(L1 == R1){
            return str1[L1] == str2[L2];
        }
        for (int leftEnd = L1; leftEnd < R1; leftEnd++) {
            boolean p1 = process(str1,L1,leftEnd,str2,L2,L2 + leftEnd - L1)
                    && process(str1,leftEnd + 1,R1,str2,L2 + leftEnd - L1 + 1,R2);
            boolean p2 = process(str1,L1,leftEnd,str2,R2 - (leftEnd - L1),R2) &&
                    process(str1,leftEnd + 1,R1,str2,L2,R2 - (leftEnd - L1) - 1);
            if(p1 || p2){
                return true;
            }
        }
        return false;
    }
    public static boolean process1(char[] str1,char[] str2,int L1,int L2,int size){
        if(size == 1){
            return str1[L1] == str2[L2];
        }
        for (int leftEnd = L1; leftEnd < size; leftEnd++) {
//            boolean p1 = process(str1,L1,leftEnd,str2,L2,L2 + leftEnd - L1)
//                    && process(str1,leftEnd + 1,L1 + size,str2,L2 + leftEnd - L1 + 1,R2);
//            boolean p2 = process(str1,L1,leftEnd,str2,R2 - (leftEnd - L1),R2) &&
//                    process(str1,leftEnd + 1,R1,str2,L2,R2 - (leftEnd - L1) - 1);
//            if(p1 || p2){
//                return true;
//            }
        }
        return false;
    }

    public static boolean sameTypeSameNumber(char[] str1, char[] str2) {
        if (str1.length != str2.length) {
            return false;
        }
        int[] map = new int[256];
        for (int i = 0; i < str1.length; i++) {
            map[str1[i]]++;
        }
        for (int i = 0; i < str2.length; i++) {
            if (--map[str2[i]] < 0) {
                return false;
            }
        }
        return true;
    }
}
